package org.leetcode.middle.leetcode78;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution
{

    List<List<Integer>> res = new ArrayList<>();

    Deque<Integer> deq = new LinkedList<>();

    List<Integer> item = new ArrayList<>();
     public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return res;
    }


    private void backtracking3(int []nums,int index){
         res.add(new ArrayList<>(item));
         if (index>=nums.length){
             return;
         }

        for (int i = index; i < nums.length; i++) {
                item.add(nums[i]);
                backtracking3(nums,i+1);
                item.remove(item.size()-1);
        }
    }


    private void backtracking2(int [] nums,int index){
        res.add(new ArrayList<>(item));

        if (index==nums.length){
             return;
         }

        for (int i = index; i < nums.length ; i++) {
            item.add(nums[i]);

            backtracking2(nums,i+1);

            item.remove(item.size()-1);
        }

    }

    private void backtracking(int[] nums,int startIndex)
    {
        res.add(new ArrayList<>(deq));

        for (int i = startIndex; i <nums.length; i++) {

            deq.addLast(nums[i]);

            backtracking(nums,i+1);

            deq.removeLast();

        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> test = new LinkedList<>();

        test.add(1);
        test.add(2);

        test.add(5);

        System.out.println(test);
    }
}
